InforLorV4, Main, Exploration, bibRecord, 006A39

Improved hit criteria for DNA local alignment

Identifieur interne : 006A39 ( Main/Exploration ); précédent : 006A38; suivant : 006A40

Improved hit criteria for DNA local alignment

Auteurs : Laurent Noé ; Gregory Kucherov

Source :

BMC Bioinformatics [ 1471-2105 ] ; 2004.

RBID : PMC:526756

Descripteurs français

KwdFr :
- ADN (génétique), ADN bactérien (génétique), ADN fongique (génétique), Algorithmes, Alignement de séquences (), Alignement de séquences (normes), Animaux, Chaines de Markov, Chromosomes X humains (génétique), Drosophila (génétique), Humains, Modèles statistiques, Neisseria meningitidis (génétique), Saccharomyces cerevisiae (génétique).
MESH :
- génétique : ADN, ADN bactérien, ADN fongique, Chromosomes X humains, Drosophila, Neisseria meningitidis, Saccharomyces cerevisiae.
- normes : Alignement de séquences.
- Algorithmes, Alignement de séquences, Animaux, Chaines de Markov, Humains, Modèles statistiques.
mix :
- adn, alignement local, dna, graines espacées, graines à transitions, local alignment, seed sensitivity, sensibilité de la graine, spaced seeds, transition constrained seeds, yass.

English descriptors

KwdEn :
- Algorithms, Animals, Chromosomes, Human, X (genetics), DNA (genetics), DNA, Bacterial (genetics), DNA, Fungal (genetics), Drosophila (genetics), Humans, Markov Chains, Models, Statistical, Neisseria meningitidis (genetics), Saccharomyces cerevisiae (genetics), Sequence Alignment (methods), Sequence Alignment (standards).
MESH :
- chemical , genetics : DNA, DNA, Bacterial, DNA, Fungal.
- genetics : Chromosomes, Human, X, Drosophila, Neisseria meningitidis, Saccharomyces cerevisiae.
- methods : Sequence Alignment.
- standards : Sequence Alignment.
- Algorithms, Animals, Humans, Markov Chains, Models, Statistical.

Abstract

Background

The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.

Results

In this paper, we propose two ways to improve the hit criterion. First, we define the group criterion combining the advantages of the single-seed and double-seed approaches used in existing algorithms. Second, we introduce transition-constrained seeds that extend spaced seeds by the possibility of distinguishing transition and transversion mismatches. We provide analytical data as well as experimental results, obtained with the YASS software, supporting both improvements.

Conclusions

Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at .

Url:

DOI: 10.1186/1471-2105-5-149
PubMed: 15485572
PubMed Central: 526756

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">15485572</idno>
<idno type="pmc">526756</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC526756</idno>
<idno type="RBID">PMC:526756</idno>
<idno type="doi">10.1186/1471-2105-5-149</idno>
<date when="2004">2004</date>
<idno type="wicri:Area/Pmc/Corpus">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000024</idno>
<idno type="wicri:Area/Pmc/Curation">000024</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000024</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000097</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000097</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="wicri:Area/PubMed/Corpus">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000177</idno>
<idno type="wicri:Area/PubMed/Curation">000177</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000177</idno>
<idno type="wicri:Area/PubMed/Checkpoint">000162</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000162</idno>
<idno type="wicri:Area/Ncbi/Merge">000010</idno>
<idno type="wicri:Area/Ncbi/Curation">000010</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">000010</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00448743</idno>
<idno type="url">https://hal.inria.fr/inria-00448743</idno>
<idno type="wicri:Area/Hal/Corpus">002997</idno>
<idno type="wicri:Area/Hal/Curation">002997</idno>
<idno type="wicri:Area/Hal/Checkpoint">004A38</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004A38</idno>
<idno type="wicri:doubleKey">1471-2105:2004:Noe L:improved:hit:criteria</idno>
<idno type="wicri:Area/Main/Merge">006D42</idno>
<idno type="wicri:Area/Main/Curation">006A39</idno>
<idno type="wicri:Area/Main/Exploration">006A39</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Improved hit criteria for DNA local alignment</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><nlm:aff id="I1">LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy France</nlm:aff>
<wicri:noCountry code="subfield">54602 Villers-lès-Nancy France</wicri:noCountry>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2004">2004</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Chromosomes, Human, X (genetics)</term>
<term>DNA (genetics)</term>
<term>DNA, Bacterial (genetics)</term>
<term>DNA, Fungal (genetics)</term>
<term>Drosophila (genetics)</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
<term>Neisseria meningitidis (genetics)</term>
<term>Saccharomyces cerevisiae (genetics)</term>
<term>Sequence Alignment (methods)</term>
<term>Sequence Alignment (standards)</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>ADN (génétique)</term>
<term>ADN bactérien (génétique)</term>
<term>ADN fongique (génétique)</term>
<term>Algorithmes</term>
<term>Alignement de séquences ()</term>
<term>Alignement de séquences (normes)</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Chromosomes X humains (génétique)</term>
<term>Drosophila (génétique)</term>
<term>Humains</term>
<term>Modèles statistiques</term>
<term>Neisseria meningitidis (génétique)</term>
<term>Saccharomyces cerevisiae (génétique)</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="genetics" xml:lang="en"><term>DNA</term>
<term>DNA, Bacterial</term>
<term>DNA, Fungal</term>
</keywords>
<keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Chromosomes, Human, X</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>ADN</term>
<term>ADN bactérien</term>
<term>ADN fongique</term>
<term>Chromosomes X humains</term>
<term>Drosophila</term>
<term>Neisseria meningitidis</term>
<term>Saccharomyces cerevisiae</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" qualifier="normes" xml:lang="fr"><term>Alignement de séquences</term>
</keywords>
<keywords scheme="MESH" qualifier="standards" xml:lang="en"><term>Sequence Alignment</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Animals</term>
<term>Humans</term>
<term>Markov Chains</term>
<term>Models, Statistical</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Alignement de séquences</term>
<term>Animaux</term>
<term>Chaines de Markov</term>
<term>Humains</term>
<term>Modèles statistiques</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>adn</term>
<term>alignement local</term>
<term>dna</term>
<term>graines espacées</term>
<term>graines à transitions</term>
<term>local alignment</term>
<term>seed sensitivity</term>
<term>sensibilité de la graine</term>
<term>spaced seeds</term>
<term>transition constrained seeds</term>
<term>yass</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method.</p>
</sec>
<sec><title>Results</title>
<p>In this paper, we propose two ways to improve the hit criterion. First, we define the <italic>group criterion </italic>
combining the advantages of the single-seed and double-seed approaches used in existing algorithms. Second, we introduce <italic>transition-constrained seeds </italic>
that extend spaced seeds by the possibility of distinguishing transition and transversion mismatches. We provide analytical data as well as experimental results, obtained with the YASS software, supporting both improvements.</p>
</sec>
<sec><title>Conclusions</title>
<p>Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at <ext-link ext-link-type="uri" xlink:href="http://www.loria.fr/projects/YASS/"></ext-link>
.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<affiliations><list></list>
<tree><noCountry><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
</noCountry>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006A39 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006A39 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     PMC:526756
   |texte=   Improved hit criteria for DNA local alignment
}}

Pour générer des pages wiki

HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i   -Sk "pubmed:15485572" \
       | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd   \
       | NlmPubMed2Wicri -a InforLorV4

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Improved hit criteria for DNA local alignment

Improved hit criteria for DNA local alignment

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

Pour générer des pages wiki

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.